package com.elloe.数组.二分查找;

import org.junit.jupiter.api.Test;

/**
 * @author ElloeStudy(Sifa Zhang)
 * @create 2022-03-09 18:35
 * To: 真常应物，真常得性，常清常静，常清静矣
 */

// 搜索插入的位置
public class InsertDemo {
    @Test
    public void s1() {
        /**
         * 四种情况
         *     - 目标值在所有的元素之前
         *     - 目标值等于数组的某一个元素
         *     - 目标值插入数组的位置
         *     - 目标值在所有的元素之后
         */

        // 暴力法
        int target = 5, x = -1;
        int[] nums = {1, 3, 5, 6, 4};
        // 解决了前三种情况
        for (int i = 0; i < nums.length; i++) {
            if (target <= nums[i]){
                x = i;
                break;
            }
        }
        if (x==-1){  // 第四种情况
            x = nums.length;
        }
        System.out.println(x);
    }


    @Test
    public void s2(){
        // 二分查找实现 查找与插入（也是四种情况）
        int[] nums = {1,3,5,6};
        int target = 2;
        int n = nums.length;
        int low = 0, high = n-1;
        while (low<=high){
            int mid = low + (high-low)/2;
            if (nums[mid]>target){
                high = mid - 1;
            }else if (nums[mid]<target){
                low = mid + 1;
            }else{
                // 目标值与数组中的某个元素相等
                System.out.println(mid);
                return ;
            }
        }
        // 目标在数组的所有的元素之前
        // 目标值插入数组里面
        // 目标值在数组的所有的元素之后
        System.out.println(high + 1);
    }

    @Test
    public void s3(){
        // 左闭右开
        int[] nums = {1,3,5,6};
        int target = 7;
        int left = 0 , right = nums.length;
        // target在数组元素里面
        while (left<right){
            int mid = left + ((right-left)/2);
            if (target<nums[mid]){
                right = mid;
            }else if (target>nums[mid]){
                left = mid + 1;
            }else{
                System.out.println(mid);
                return;
            }
        }
        // target不在数组元素里面
        System.out.println(right);
    }
}
